SherbyNet - /page/wikibook/entry.mu

Micron Document

`:top

In `F33f`_`[structure mining`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Structure_mining]`_`f, a `!graph kernel`! is a `F33f`_`[kernel function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Positive-definite_kernel]`_`f that computes an `F33f`_`[inner product`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Inner_product_space]`_`f on `F33f`_`[graphs`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Graph_(abstract_data_type)]`_`f.`:cite-ref-vishwanathan-1-0[`F5bf`_`[1`#cite-note-vishwanathan-1]`_`f] Graph kernels can be intuitively understood as functions measuring the similarity of pairs of graphs. They allow `F33f`_`[kernelized`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Kernel_trick]`_`f learning algorithms such as `F33f`_`[support vector machines`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Support_vector_machine]`_`f to work directly on graphs, without having to do `F33f`_`[feature extraction`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Feature_extraction]`_`f to transform them to fixed-length, real-valued `F33f`_`[feature vectors`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Feature_vector]`_`f. They find applications in `F33f`_`[bioinformatics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bioinformatics]`_`f, in `F33f`_`[chemoinformatics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Chemoinformatics]`_`f (as a type of `F33f`_`[molecule kernels`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Molecule_kernel]`_`f`:cite-ref-ralaivola2005-2-0[`F5bf`_`[2`#cite-note-ralaivola2005-2]`_`f]), and in `F33f`_`[social network analysis`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Social_network_analysis]`_`f.`:cite-ref-vishwanathan-1-1[`F5bf`_`[1`#cite-note-vishwanathan-1]`_`f]

Concepts of graph kernels have been around since the 1999, when D. Haussler`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f] introduced convolutional kernels on discrete structures. The term graph kernels was more officially coined in 2002 by R. I. Kondor and `F33f`_`[J. Lafferty`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=John_D._Lafferty]`_`f`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f] as kernels `*on`* graphs, i.e. similarity functions between the nodes of a single graph, with the `F33f`_`[World Wide Web`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=World_Wide_Web]`_`f `F33f`_`[hyperlink`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hyperlink]`_`f graph as a suggested application. In 2003, Gärtner `*et al.`*`:cite-ref-gaertner-5-0[`F5bf`_`[5`#cite-note-gaertner-5]`_`f] and Kashima `*et al.`*`:cite-ref-kashima-6-0[`F5bf`_`[6`#cite-note-kashima-6]`_`f] defined kernels `*between`* graphs. In 2010, Vishwanathan `*et al.`* gave their unified framework.`:cite-ref-vishwanathan-1-2[`F5bf`_`[1`#cite-note-vishwanathan-1]`_`f] In 2018, Ghosh et al. `:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f] described the history of graph kernels and their evolution over two decades.

>>Contents

• `F0af`_`[Applications`#applications]`_`f

• `F0af`_`[Example Kernels`#example-kernels]`_`f

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>Applications

The marginalized graph kernel has been shown to allow accurate predictions of the atomization energy of small organic molecules.`:cite-ref-8[`F5bf`_`[8`#cite-note-8]`_`f]

>>Example Kernels

An example of a kernel between graphs is the `!random walk kernel`!,`:cite-ref-gaertner-5-1[`F5bf`_`[5`#cite-note-gaertner-5]`_`f]`:cite-ref-kashima-6-1[`F5bf`_`[6`#cite-note-kashima-6]`_`f] which conceptually performs `F33f`_`[random walks`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Random_walk]`_`f on two graphs simultaneously, then counts the number of `F33f`_`[paths`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Path_(graph_theory)]`_`f that were produced by `*both`* walks. This is equivalent to doing random walks on the `F33f`_`[direct product`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Tensor_product_of_graphs]`_`f of the pair of graphs, and from this, a kernel can be derived that can be efficiently computed.`:cite-ref-vishwanathan-1-3[`F5bf`_`[1`#cite-note-vishwanathan-1]`_`f]

Another examples is the `!Weisfeiler-Leman graph kernel`!`:cite-ref-9[`F5bf`_`[9`#cite-note-9]`_`f] which computes multiple rounds of the `F33f`_`[Weisfeiler-Leman algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Weisfeiler-Leman_algorithm]`_`f and then computes the similarity of two graphs as the inner product of the histogram vectors of both graphs. In those histogram vectors the kernel collects the number of times a color occurs in the graph in every iteration. Note that the Weisfeiler-Leman kernel in theory has an infinite dimension as the number of possible colors assigned by the Weisfeiler-Leman algorithm is infinite. By restricting to the colors that occur in both graphs, the computation is still feasible.

>>See also

• `F33f`_`[Tree kernel`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Tree_kernel]`_`f, as special case of non-cyclic graphs

• `F33f`_`[Molecule mining`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Molecule_mining]`_`f, as special case of small multi-label graphs

>>References

`:cite-note-vishwanathan-1`!1.`! `F0af`_`[↑`#cite-ref-vishwanathan-1-0]`_`f `:citerefs-v-n-vishwanathannicol-n-schraudolphrisi-kondorkarsten-m-borgwardt2010`aS.V. N. Vishwanathan; Nicol N. Schraudolph; Risi Kondor; `F33f`_`[Karsten M. Borgwardt`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Karsten_Borgwardt]`_`f (2010). "Graph kernels" (PDF). `*`F33f`_`[Journal of Machine Learning Research`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Journal_of_Machine_Learning_Research]`_`f`*. `!11`!: 1201–1242.

`:cite-note-ralaivola2005-2`!2.`! `F0af`_`[↑`#cite-ref-ralaivola2005-2-0]`_`f `:citerefl-ralaivolas-j-swamidassh-saigop-baldi2005`aL. Ralaivola; S. J. Swamidass; H. Saigo; P. Baldi (2005). "Graph kernels for chemical informatics". `*Neural Networks`*. `!18`! (8): 1093–1110. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/j.neunet.2005.07.009. `F33f`_`[PMID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PMID_(identifier)]`_`f 16157471.

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f `:citerefhaussler1999`aHaussler, David (1999). `*Convolution Kernels on Discrete Structures`*. `F33f`_`[CiteSeerX`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=CiteSeerX_(identifier)]`_`f 10.1.1.110.638.

`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f `:citerefrisi-imre-kondorjohn-lafferty2002`aRisi Imre Kondor; John Lafferty (2002). `*Diffusion Kernels on Graphs and Other Discrete Input Spaces`* (PDF). Proc. Int'l Conf. on Machine Learning (ICML).

`:cite-note-gaertner-5`!5.`! `F0af`_`[↑`#cite-ref-gaertner-5-0]`_`f `:citerefthomas-g-rtnerpeter-a-flachstefan-wrobel2003`aThomas Gärtner; Peter A. Flach; Stefan Wrobel (2003). `*On graph kernels: Hardness results and efficient alternatives`*. Proc. the 16th Annual Conference on Computational Learning Theory (COLT) and the 7th Kernel Workshop. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/978-3-540-45167-9_11.

`:cite-note-kashima-6`!6.`! `F0af`_`[↑`#cite-ref-kashima-6-0]`_`f `:citerefhisashi-kashimakoji-tsudaakihiro-inokuchi2003`aHisashi Kashima; Koji Tsuda; Akihiro Inokuchi (2003). `*Marginalized kernels between labeled graphs`* (PDF). Proc. the 20th International Conference on Machine Learning (ICML).

`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f `:citerefghoshdasgon-alvesquaresma2018`aGhosh, Swarnendu; Das, Nibaran; Gonçalves, Teresa; Quaresma, Paulo; Kundu, Mahantapas (2018). "The journey of graph kernels through two decades". `*Computer Science Review`*. `!27`!: 88–111. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/j.cosrev.2017.11.002.

`:cite-note-8`!8.`! `F0af`_`[↑`#cite-ref-8]`_`f `:citerefyu-hang-tangwibe-a-de-jong2019`aYu-Hang Tang; Wibe A. de Jong (2019). "Prediction of atomization energy using graph kernel and active learning". `*The Journal of Chemical Physics`*. `!150`! (4): 044107. `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:1810.07310. `F33f`_`[Bibcode`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bibcode_(identifier)]`_`f:2019JChPh.150d4107T. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1063/1.5078640. `F33f`_`[PMID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PMID_(identifier)]`_`f 30709286.

`:cite-note-9`!9.`! `F0af`_`[↑`#cite-ref-9]`_`f Shervashidze, Nino, et al. "Weisfeiler-lehman graph kernels." Journal of Machine Learning Research 12.9 (2011).

`c`F0af`_`[↑ Back to top`#top]`_`f`a